import java.util.Arrays;

public class test {
    //插入排序方法一:时间复杂度为O(n^2);空间复杂度为O(1)；稳定
    public static void paixu1(int arr[]){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
                else {
                    break;
                }
            }
        }
    }
    // 插入排序方法二:时间复杂度为O(n^2);空间复杂度为O(1)；稳定
    public static void paixu2(int arr[]){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }
                else {
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    //希尔排序；时间复杂度为O(n*logn);空间复杂度为O(1);不稳定
    public static void haset(int arr[]) {
        int gap = arr.length;
        while (gap >1) {
            gap /= 2;
            hpa(arr,gap);
        }
    }
    private  static void hpa(int arr[],int gap){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }
                else {
                    break;
                }
            }
            arr[j+gap]=temp;
        }
    }
    //选择排序:时间复杂度为O(n^2);空间复杂度为O(1);不稳定
    public static void xtion1(int arr[]){
        for (int i=0;i< arr.length;i++){
            int temp=i;
            for (int j=i+1;j< arr.length;j++){
                if(arr[j]<arr[temp]) {
                    temp= j;
                }
            }
            if(arr[temp]<arr[i]){
                swap(arr,i,temp);
            }
        }
    }
    public static void xtion2(int arr[]){
        int left=0;
        int right=arr.length-1;
        while(left<right){
            int minindex= left;
            int maxindex=left;//用maxindex=right就需要去套两个for循环增加运行时间
            for(int i=left+1;i<=right;i++){
                if(arr[i]<arr[minindex]){
                    minindex=i;
                }
                if(arr[i]>arr[maxindex]){
                    maxindex=i;
                }
            }
            swap(arr,left,minindex);
            //第一个数是最大值
            if(left==maxindex){
                maxindex=minindex;
            }
            swap(arr,right,maxindex);
            left++;
            right--;
        }
    }
    //堆排序:时间复杂度为O(n*logn)；空间复杂度为O(1);不稳定
    public static void duipa(int []arr){
        int end= arr.length-1;
        dadui(arr,end);
        while (end>0){
            swap(arr,0,end);
            dadui(arr,end);
            end--;
        }
    }
    private static void dadui(int []arr,int end){
        int usize= end;
        for (int parten=(usize-1)/2;parten>=0;parten--){
            int childer=parten*2+1;
            while(childer<usize){
                if(childer+1<usize&&arr[childer]<arr[childer+1]){
                    childer++;
                }
                if(arr[parten]<arr[childer]){
                    swap(arr,parten,childer);
                    parten=childer;
                    childer=parten*2+1;
                }
                else{
                    break;
                }
            }
        }
    }
    private static void swap(int arr[],int ret1,int ret2){
        int temp=arr[ret1];
        arr[ret1]=arr[ret2];
        arr[ret2]=temp;
    }

    public static void main(String[] args) {
        int []arr1={5,6,4,2,7,9,1,2};
        paixu1(arr1);
        System.out.println(Arrays.toString(arr1));
        int []arr2={64,45,15,51,1,5,31};
        paixu2(arr2);
        System.out.println(Arrays.toString(arr2));
        int []arr3={64,45,15,51,1,5,31,88,46,95};
        haset(arr3);
        System.out.println(Arrays.toString(arr3));
        int []arr4={64,45,15,51,1,5,31,88,46,95};
        xtion1(arr4);
        System.out.println(Arrays.toString(arr4));
        int []arr5={10,6,4,2,7,9,1,2};
        xtion2(arr5);
        System.out.println(Arrays.toString(arr5));
        int []arr6={8,6,4,2,7,9,1,2};
        duipa(arr6);
        System.out.println(Arrays.toString(arr6));
    }
}
